#ifndef __ARBOL_B_H__
#define __ARBOL_B_H__ 

#include <string>
#include <fstream>
#include <utility>
#include <map>
#include <list>
#include "BloqueSequenceSet.h"
#include "BloqueIndexSet.h"
#include "Archivo.h"
#include "Cache.h"

#include <sstream>

using namespace std;

template<class Clave,class Dato>
class ArbolBMas
{

public:

	/**
	 * Se obtienen los bloques borrados del index set y del sequence set.
	 */
	void getBloquesBorrados(istream &is,list<long> &listadoBloques)
	{
		long cantidad;
		long posicionBloqueBorrado;
		
		// Se obtiene la cantidad de posiciones a leer.
		is.read((char *)&cantidad,sizeof(long));
		
		// Se obtienen las posiciones de los bloques borrados.
		for(long i=0;i<cantidad;i++)
		{
			is.read((char *)&posicionBloqueBorrado,sizeof(long));
			listadoBloques.push_back(posicionBloqueBorrado);
		}
	}

	/**
	* Crea un arbol B+ del orden especificado. Si el archivo ya existe se
	* intenta obtener los datos del mismo. Sino se crea el archivo.
	* @param archivo Ruta y nombre a partir del cual se generaran los archivos 
	* para contener los datos del index set y del sequence set.
	* @param orden Orden del arbol B+ a ser creado. En caso de existir debe 
	* concordar con el orden especificado en el archivo.
	*/
	ArbolBMas(const string &archivo,const long bloquesCacheIndexSet=2000,
		const long bloquesCacheSequenceSet=8000,const short orden=7):
	archivo(archivo),
	_eof(true),
	bloqueActual(orden),
	cacheIndexSet(bloquesCacheIndexSet),
	cacheSequenceSet(bloquesCacheSequenceSet)
	{
		string archivoIndexSet=archivo+".ind";
		string archivoSequenceSet=archivo+".seq";
		string archivoBloquesBorrados=archivo+".del";
		fstream bloquesBorrados;

		abrirArchivoBinario(this->indexSet,archivoIndexSet);
		abrirArchivoBinario(this->sequenceSet,archivoSequenceSet);
		abrirArchivoBinario(bloquesBorrados,archivoBloquesBorrados);

		// Se intenta obtener la raiz del index set.
		try
		{
			this->indexSet.read((char *)&(this->orden),sizeof(short));
			this->indexSet.read((char *)&(this->altura),sizeof(long));
			this->indexSet.read((char *)&(this->raizIndexSet),sizeof(long));
			
			BloqueSequenceSet<Clave,Dato> bloqueActual(this->orden);  
			
			this->bloqueActual=bloqueActual;
		}
		catch(...)
		{
			this->orden=orden;
			this->altura=0;
			this->raizIndexSet=-1;

			this->writeIndexSet();
		}

		// Se intenta obtener el primero del sequence set.
		try
		{
			this->sequenceSet.read((char *)&(this->primeroSequenceSet),
				sizeof(long));
		}
		catch(...)
		{
			this->primeroSequenceSet=-1;

			this->writeSequenceSet();
		}
		
		try
		{
			this->getBloquesBorrados(bloquesBorrados,this->borradosIndexSet);
			this->getBloquesBorrados(bloquesBorrados,this->borradosSequenceSet);
		}
		catch(...)
		{
		}
		
		bloquesBorrados.close();
		this->archivosCerrados = false;
	}

	/**
	 * Se guardan los bloques borrados.
	 */
	void writeBloquesBorrados(ostream &os,const list<long> &borrados)
	{
		long posicionBloqueBorrado;
		long cantidad=borrados.size();
		
		os.write((char *)&cantidad,sizeof(long));
		
		list<long>::const_iterator i;
		for(i=borrados.begin();i!=borrados.end();i++)
		{
			posicionBloqueBorrado=*i;
			os.write((char *)&posicionBloqueBorrado,sizeof(long));
		}
	}

	/*
	* Si los archivos no estar cerrados, se guardan los datos del index set y del sequence set. Se cierran los 
	* archivos. 
	* Se elimina a this.
	*/
	~ArbolBMas() 
	{
		if (!(this->archivosCerrados))
			this->cerrar();
	}
	
	/**
	* Se guardan los datos del index set y del sequence set. Se cierran los 
	* archivos.
	*/
	void cerrar()
	{
		// Se guardan los datos de los bloques que se encuentran en el cache.
		this->guardarDatosCache(this->cacheIndexSet,this->indexSet);
		this->guardarDatosCache(this->cacheSequenceSet,this->sequenceSet);

		// Se guardan los datos de cabecera del arbol.
		this->writeIndexSet();
		this->writeSequenceSet();
		
		string archivoBloquesBorrados=this->archivo+".del";
		fstream bloquesBorrados;
		crearArchivoBinario(bloquesBorrados,archivoBloquesBorrados);

		// Se guardan las posiciones de los bloques borrados.
		this->writeBloquesBorrados(bloquesBorrados,this->borradosIndexSet);
		this->writeBloquesBorrados(bloquesBorrados,this->borradosSequenceSet);
		
		bloquesBorrados.close();

		
		// Se cierran los streams.
		this->indexSet.close();
		this->sequenceSet.close();
		archivosCerrados = true;
	}

	/**
	 * Se elimina el arbol especificado en archivo.
	 * @param archivo Ruta y nombre del archivo utilizados para crear el arbol
	 * B+ que se desea eliminar.
	 */
	static void borrar(const string &archivo)
	{
		string archivoIndexSet=archivo+".ind";
		string archivoSequenceSet=archivo+".seq";

		std::remove(archivoIndexSet.c_str());
		std::remove(archivoSequenceSet.c_str());
	}
	
	static void duplicarArchivos(const string &archivo)
	{
		string archivoIndexSet=archivo+".ind";
		string archivoSequenceSet=archivo+".seq";
		string archivoIndexSetCopia=archivoIndexSet+".backup";
		string archivoSequenceSetCopia=archivoSequenceSet+".backup";
		{
			fstream original;
			original.open(archivoIndexSet.c_str(),fstream::in | fstream::out | fstream::binary);
			fstream copia;
			copia.open(archivoIndexSetCopia.c_str(),fstream::out | fstream::binary);
			if(original.is_open()&&copia.is_open())
				copia<<original.rdbuf();
		}
		{
			fstream original;
			original.open(archivoSequenceSet.c_str(),fstream::in | fstream::out | fstream::binary);
			fstream copia;
			copia.open(archivoSequenceSetCopia.c_str(),fstream::out | fstream::binary);
			if(original.is_open()&&copia.is_open())
				copia<<original.rdbuf();
		}
	}
	
	static void borrarCopia(const string &archivo)
	{
		string archivoIndexSet=archivo+".ind.backup";
		string archivoSequenceSet=archivo+".seq.backup";

		std::remove(archivoIndexSet.c_str());
		std::remove(archivoSequenceSet.c_str());
	}
	
	static void renombrarArchivos(const string &archivo)
	{
		string archivoIndexSet=archivo+".ind";
		string archivoSequenceSet=archivo+".seq";
		string archivoIndexSetCopia=archivoIndexSet+".backup";
		string archivoSequenceSetCopia=archivoSequenceSet+".backup";

		rename(archivoIndexSetCopia.c_str(),archivoIndexSet.c_str());
		rename(archivoSequenceSetCopia.c_str(),archivoSequenceSet.c_str());
	}
	
	/**
	* Se inserta el dato asociado a la clave pasada en el arbol. En caso de 
	* tener exito se verifica !(this->eof()). En caso de existir la clave 
	* pasada se verifica this->eof().
	* @param clave Clave a ser agregada al arbol.
	* @param dato Dato a ser agregado en el arbol.
	*/
	void insert(const Clave &clave,const Dato &dato)
	{
		// En caso de estar vacio el arbol se agrega el primer bloque del
		// sequence set.
		if (this->vacio())
		{
			BloqueSequenceSet<Clave,Dato> bloque(this->orden);

			// Se inserta la clave junto con el dato en el bloque.
			bloque.insert(clave,dato);

			// Se setea el cursor al final del archivo del sequence set.
			//this->sequenceSet.seekp(0,ios_base::end);
			
			// Se setea el cursor en un bloque vac�o del sequence set.
			this->setCursorBloqueVacioSequenceSet();
			
			
			// Se obtiene la posicion del primero del sequence set (el bloque 
			// a ser agregado).
			this->primeroSequenceSet=this->sequenceSet.tellp();
			
			// Se setea la altura.
			this->altura=1;

			// Se agrega el bloque al arbol
			this->addBloqueSequenceSet(bloque);
			
			// Se indica se tuvo exito.
			this->_eof=false;
		}
		else
		{
			Dato tmpDato;
			
			// Se verifica si existe la clave pasada y, a su vez, se obtienen 
			// los datos del bloque, en this->bloqueActual, donde se deberia 
			// insertar la clave en caso de corresponder.    
			this->readIgual(tmpDato,clave);
			
			// En caso de existir la clave...
			if (!this->eof())
			{
				// ...se indica el error.
				this->_eof=true;
				// Se finaliza la rutina.
				return;
			}
			
			// Sino se prosigue con la insercion.
			
			// En caso de estar lleno el bloque habra que dividirlo.
			if (this->bloqueActual.lleno())
				// Se hace un split del bloque generando un nuevo bloque.
				this->splitBloqueSequenceSet(this->bloqueActual,clave,dato);
			else 
			{
				// Se agregan la clave y el dato en el bloque del sequence set.
				this->bloqueActual.insert(clave,dato);

				this->actualizarBloqueSequenceSet(this->bloqueActual);
			}
			this->_eof=false;
		}		
	}
	

	/**
	* Se modifica el dato asociado a la clave pasada en el arbol. En caso de 
	* tener exito se verifica !(this->eof()). En caso de no existir la clave 
	* pasada se verifica this->eof().
	* @param clave Clave a ser modificada en el arbol.
	* @param dato Dato a ser modificado en el arbol.
	*/
	void update(const Clave &clave,const Dato &dato)
	{
		Dato tmpDato;
			
		// Se verifica si existe la clave pasada y, a su vez, se obtienen 
		// los datos del bloque, en this->bloqueActual, donde se deberia 
		// modificar el dato en caso de corresponder.    
		this->readIgual(tmpDato,clave);
			
		// En caso de no existir la clave...
		if (this->eof())
		{
			// ...se indica el error.
			this->_eof=true;
			// Se finaliza la rutina.
			return;
		}
			
		// Sino se prosigue con la modificacion.
			
		// Se modifica el dato en el bloque del sequence set.
		this->bloqueActual.update(clave,dato);

		this->actualizarBloqueSequenceSet(this->bloqueActual);

		this->_eof=false;
		
	}

	/**
	* Verifica si encuentra la clave pasada. En caso de encontrarla
	* setea el cursor en el bloque donde se encuentra el dato de dicha
	* clave, sino setea el cursor en el bloque con clave inmediatamente
	* mayor. El bloque actual es el bloque que contiene la clave igual o 
	* inmediatamente mayor a la pasada y dicho bloque tiene el cursor a 
	* puntando a la clave correspondiente
	* @param dato Dato recuperado si se encuentra la clave.
	* @param clave Clave a buscar en el arbol.
	*/
	void readIgual(Dato &dato,const Clave &clave)
	{
		if (this->vacio())
			this->_eof=true;
		else
		{
			// En caso de que la altura de this sea mayor que 1, significa que 
			// se debe acceder a los bloques del index set para llegar al dato
			// buscado
			if (this->altura>1)
			{
				// Se obtiene el bloque raiz del index set.
				BloqueIndexSet<Clave> bloque(this->orden);
				
				this->getRaizIndexSet(bloque);

				// Se obtiene un bloque del index set del ultimo nivel.
				for (int i=1;i<(this->altura-1);i++)
					// Se obtiene el bloque hijo correspondiente en funcion a
					// la clave pasada.
					this->getBloqueIndexSet(bloque,bloque.getHijo(clave));

				// ...se obtiene el bloque hijo, el que se encuentra en el
				// sequence set.
				this->getBloqueSequenceSet(this->bloqueActual,
					bloque.getHijo(clave));
			}
			else
				this->getPrimeroSequenceSet(this->bloqueActual);

			// Se intenta obtener el dato del bloque donde deberia estar
			// la clave pasada.
			this->bloqueActual.readIgual(dato,clave);

			this->_eof=this->bloqueActual.eof();
		}
	}

	/**
	* Verifica si encuentra la clave pasada. En caso de encontrarla
	* setea el cursor en el dato correspondiente. Setea el cursor en el 
	* bloque donde existe o deberia existir dicha clave, es decir
	* this->bloqueActual es el bloque donde deberia existir la clave. Si no 
	* encontro la clave buscada se verifica this->eof().
	* @param dato Dato recuperado si se encuentra la clave.
	* @param clave Clave a buscar en el arbol.
	*/
	void readMayorIgual(Dato &dato,const Clave &clave)
	{
		// Trata de posicionarse en la clave pasada.
		this->readIgual(dato,clave);

		// En caso de no haber podido...
		if (this->eof())
		{
			this->bloqueActual.find(clave);

			// En caso de no haber encontrado una clave mayor...
			if (this->bloqueActual.eof())
			{
				// ...se verifica si hay un bloque siguiente al bloque en
				// cuestion, en caso de ser asi.
				if (this->bloqueActual.tieneBloqueDerecho())
				{
					// Se obtiene dicho bloque.
					this->getBloqueSequenceSet(this->bloqueActual,
						this->bloqueActual.getBloqueDerecho());

					// Se posiciona en el primer elemento del bloque obtenido,
					// que seguro tiene clave mayor a la buscada.
					this->bloqueActual.first();
				}
			}

			// En caso de haber encontrado una clave mayor...
			if (!(this->bloqueActual.eof()))
				// ...se obtiene el dato para dicha clave.
				dato=this->bloqueActual.getDato();

			// Se setea la marca de fin de archivo.
			this->_eof=this->bloqueActual.eof();
		}
	}

	/**
	 * Elimina la clave pasada del arbol.
	 * @param Clave a ser eliminada.
	 */	
	void erase(const Clave &clave)
	{
		Dato dato;
		
		this->readIgual(dato,clave);
		
		// En caso de haber encontrado la clave a eliminar...
		if (!this->eof())
		{
			// En caso de que el arbol tenga altura mayor a 1...
			if (this->altura>1)
			{ 							
				// En caso de que la cantidad de claves sea minima...
				if (this->bloqueActual.tieneCantidadMinimaClaves())
				{
					BloqueSequenceSet<Clave,Dato> hermano(this->orden);
					
					// Se intenta obtener una clave de alguno de los bloques a los 
					// laterales...
					if (!this->getClaveFromHermano(this->bloqueActual))
						// En caso de no haber podido, se unen dos bloques.
						this->unirConHermanoSequenceSet(this->bloqueActual);
				}
				
				// En caso de que se trate de la primer clave del bloque y el 
				// bloque no sea el primero del sequence set...
				if (this->bloqueActual.esPrimerClave(clave)&&
					(!this->esPrimerBloqueSequenceSet(this->bloqueActual)))
				{
					//try
					//{
						// Se modifica la clave en el index set por la siguiente...
						this->modificarClaveIndex(this->bloqueActual.getPadre(),
							this->bloqueActual.getSegundaClave(),clave);
					//}
					//catch(string s)
					//{
						//this->mostrar(cout);
						//cout << "Bloque actual (no modificado en arbol): " << this->bloqueActual << endl;
						//throw s;
					//}
				}

				// Se elimina la clave del bloque.
				this->bloqueActual.erase(clave);
				this->actualizarBloqueSequenceSet(this->bloqueActual);
			}
			else
			{
				// Se elimina la clave del bloque.
				this->bloqueActual.erase(clave);
				
				// En caso de quedar vac�o el bloque...
				if (this->bloqueActual.vacio())
				{
					// ...se lo elimina.
					this->eliminarBloqueSequenceSet(this->bloqueActual);
				
					this->primeroSequenceSet=-1;
				}
				
				this->actualizarBloqueSequenceSet(this->bloqueActual);
			}
		}
	}

	/**
	 * Se posiciona en el primer bloque del sequence set, y en la primer clave 
	 * de dicho bloque.
	 * El bloque actual contendra los datos de dicho bloque.
	 */
	void first()
	{
		if (!(this->_eof=this->vacio()))
		{
			this->getPrimeroSequenceSet(this->bloqueActual);
			this->bloqueActual.first();
		}
	}

	/**
	 * Posiciona el cursor en la siguiente clave del arbol.
	 * El bloque actual seguira siendo el mismo o sera el bloque a su derecha.
	 */
	void next()
	{
		// En caso de no haber llegado al final del bloque, se pide pasar a la 
		// siguiente clave...
		if (!this->bloqueActual.eof())
			this->bloqueActual.next();

		// Si se llego al final del bloque...
		if (this->bloqueActual.eof())
		{
			// En caso de tener bloque derecho...
			if (this->bloqueActual.tieneBloqueDerecho())
			{
				
				// ...se obtiene el bloque derecho.
				this->getBloqueSequenceSet(this->bloqueActual,
					this->bloqueActual.getBloqueDerecho());

				// Se posiciona en la primer clave del bloque obtenido.
				this->bloqueActual.first();
			}
			else
				// Se activa eof.
				this->_eof=true;
		}
	}

	/**
	* Indica si el cursor actual es valido.
	* @return false si el cursor actual es valido, sino true.
	*/
	bool eof()
	{
		return this->_eof;
	}

	/**
	 * Obtiene la clave a la que apunta el cursor.
	 * @return Clave a la que apunta el cursor.
	 */
	Clave getClave()
	{
		return this->bloqueActual.getClaveActual();
	}
	
	/**
	 * Obtiene el dato al que apunta el cursor.
	 * @return Dato al que apunta el cursor.
	 */
	Dato getDato()
	{
		return this->bloqueActual.getDato();
	}
	
	/**
	 * Se muestra el arbol en pre orden.
	 * @param os stream de salida en el que se mostrara el arbol.
	 * @param bloque Bloque a ser mostrado.
	 * @param nivel Nivel del bloque pasado.
	 */
	void mostrar(ostream &os)
	{
		if (!this->vacio())
		{
			if (this->altura==1)
			{
				BloqueSequenceSet<Clave,Dato> bloque(this->orden);
				this->getPrimeroSequenceSet(bloque);
//				bloque.mostrar(os);
				os << bloque; 
			}
			else
			{
				BloqueIndexSet<Clave> bloque(this->orden);
				this->getRaizIndexSet(bloque);
				this->mostrarPreOrden(os,bloque,1);
			}
		}
	}
	
	/**
	* Indica si this esta vacio.
	* @param true si esta vacio, sino false.
	*/
	bool vacio() const
	{
		return this->primeroSequenceSet<0;
	}

	/**
	 * Indica si this es consistente.
	 */
	void consistente()
	{
		try
		{
			if (!this->vacio())
			{
				if (this->altura==1)
				{
					BloqueSequenceSet<Clave,Dato> bloque(this->orden);
					this->getPrimeroSequenceSet(bloque);
					if (bloque.tieneBloqueDerecho())
						throw string("La altura del arbol es 1 y el unico bloque ")+
						"del sequence set, tiene hermano derecho";
					if (bloque.tieneBloqueIzquierdo())
						throw string("La altura del arbol es 1 y el unico bloque ")+
						"del sequence set, tiene hermano izquierdo";
					if (bloque.tienePadre())
						throw string("La altura del arbol es 1 y el unico bloque ")+
						"del sequence set, tiene padre";
				}
				else
				{
					BloqueIndexSet<Clave> bloque(this->orden);
					this->getRaizIndexSet(bloque);
					this->consistentePreOrden(bloque,1);
				}
			}
		}
		catch(string s)
		{
			throw string("Arbol inconsistente: ")+s;
		}
	}

	/**
	 * Se obtiene el nombre del archivo del index set a partir del nombre
	 * pasado.
	 * @param archivo Ruta y nombre de un archivo (el utilizado en
	 * el constructor del arbol).
	 * @return Ruta y nombre del archivo del index set.
	 */
	static string getArchivoIndexSet(const string &archivo)
	{
		return archivo+".ind";
	}

	/**
	 * Se obtiene el nombre del archivo del sequence set a partir del nombre
	 * pasado.
	 * @param archivo Ruta y nombre de un archivo (el utilizado en
	 * el constructor del arbol).
	 * @return Ruta y nombre del archivo del sequence set.
	 */
	static string getArchivoSequenceSet(const string &archivo)
	{
		return archivo+".seq";
	}

	/**
	 * Obtiene el valor del ultimo nivel del indexset.
	 * @return Valor del ultimo nivel del indexset.
	 */
	long ultimoNivelIndexSet()
	{
		return altura-1;
	}
	
	protected:

	string archivo;

	//flag de archivos cerrados
	bool archivosCerrados;
	
	// Orden del arbol.
	short orden;

	// Altura del arbol. Cuando esta vacio su altura es cero.
	long altura;

	// raices de los sets del arbol.
	long raizIndexSet;
	long primeroSequenceSet;

	// Indicador de fin de archivo.
	bool _eof;

	// Bloque actual en el que esta posicionado el cursor del arbol.
	BloqueSequenceSet<Clave,Dato> bloqueActual;

	// Archivos que contienen los distintos bloques del arbol.
	fstream indexSet;
	fstream sequenceSet;
	
	fstream bloquesBorrados;
	
	Cache<long,BloqueIndexSet<Clave> > cacheIndexSet;
	Cache<long,BloqueSequenceSet<Clave,Dato> > cacheSequenceSet;
	
	list<long> borradosIndexSet;
	list<long> borradosSequenceSet;
	
	/**
	 * Se guardan los datos del cache pasado en el ostream pasado.
	 */
	template <class Bloque>
	void guardarDatosCache(Cache<long,Bloque> &cache,ostream &os)
	{
		cache.first();
		
		while (!cache.eof())
		{
			Bloque bloque;
			cache.getDato(bloque);
			bloque.write(os);
			cache.next();
		}
	}

	/**
	 * Se agrega un bloque al sequence set.
	 * @param bloque Bloque a ser agregado.
	 */
	void addBloqueSequenceSet(BloqueSequenceSet<Clave,Dato> &bloque)
	{
		// Se guarda el bloque
		bloque.write(this->sequenceSet);
		
		this->actualizarBloqueSequenceSet(bloque);
	}
	
	/**
	 * Se actualiza un bloque del sequence set.
	 * @param bloque Bloque a ser actualizado.
	 */
	void actualizarBloqueSequenceSet(
		const BloqueSequenceSet<Clave,Dato> &bloque)
	{
		long posicionEliminada;
		BloqueSequenceSet<Clave,Dato> bloqueEliminado(this->orden);
		bool eliminado;
		
		// Se actualiza el bloque en el cache.
		cacheSequenceSet.update(bloque.getPosicion(),bloque,posicionEliminada,
			bloqueEliminado,eliminado);
		
		// Si se elimino algun bloque del cache...
		if (eliminado)
			// Se actualizan los datos del bloque eliminado en el sequence set
			bloqueEliminado.write(this->sequenceSet);
	}

	/**
	 * Setea el cursor del stream del sequence set en un bloque vac�o. En caso 
	 * de no existir bloques vac�os lo setea al final de stream.
	 * Actualiza el listado de bloques vac�os del stream quitando el bloque en 
	 * cuesti�n. 
	 */
	void setCursorBloqueVacioSequenceSet()
	{
		// En caso de estar vac�o el listado de bloques borrados...
		if (this->borradosSequenceSet.empty())
			// ...se posiciona el cursor al final del archivo.
			this->sequenceSet.seekp(0,ios_base::end);
		else
		{
			// Sino se setea el cursor en la posici�n del bloque vac�o...
			this->sequenceSet.seekp(this->borradosSequenceSet.front());
			
			// ...se quita la posici�n de la lista de bloques borrados. 
			this->borradosSequenceSet.pop_front();
		}
			
	}

	/**
	 * Setea el cursor del stream del index set en un bloque vac�o. En caso 
	 * de no existir bloques vac�os lo setea al final de stream.
	 * Actualiza el listado de bloques vac�os del stream quitando el bloque en 
	 * cuesti�n. 
	 */
	void setCursorBloqueVacioIndexSet()
	{
		// En caso de estar vac�o el listado de bloques borrados...
		if (this->borradosIndexSet.empty())
			// ...se posiciona el cursor al final del archivo.
			this->indexSet.seekp(0,ios_base::end);
		else
		{
			// Sino se setea el cursor en la posici�n del bloque vac�o...
			this->indexSet.seekp(this->borradosIndexSet.front());
			
			// ...se quita la posici�n de la lista de bloques borrados. 
			this->borradosIndexSet.pop_front();
		}
			
	}

	void actualizarBloqueIndexSet(const BloqueIndexSet<Clave> &bloque)
	{
		long posicionEliminada;
		BloqueIndexSet<Clave> bloqueEliminado(this->orden);
		bool eliminado;
		
		// Se actualiza el bloque en el cache.
		cacheIndexSet.update(bloque.getPosicion(),bloque,posicionEliminada,
			bloqueEliminado,eliminado);
		
		// Si se elimino algun bloque del cache...
		if (eliminado)
			// Se actualizan los datos del bloque eliminado en el sequence set
			bloqueEliminado.write(this->indexSet);
	}

	void getBloqueIndexSet(BloqueIndexSet<Clave> &bloque,const long posicion)
	{
		// En caso de no obtener el bloque del cache... 
		if (!this->cacheIndexSet.get(bloque,posicion))
		{
			// Se obtiene el bloque del index set
			bloque.clear();
			bloque.setPosicion(posicion);
			bloque.read(this->indexSet);
		
			// Se agrega el bloque obtenido al cache del index set.	
			this->actualizarBloqueIndexSet(bloque);
		}
	}

	void getBloqueSequenceSet(BloqueSequenceSet<Clave,Dato> &bloque,const long posicion)
	{
		// En caso de no obtener el bloque del cache... 
		if (!this->cacheSequenceSet.get(bloque,posicion))
		{
			// Se obtiene el bloque del sequence set
			bloque.clear();
			bloque.setPosicion(posicion);
			bloque.read(this->sequenceSet);
		
			// Se agrega el bloque obtenido al cache del sequence set.	
			this->actualizarBloqueSequenceSet(bloque);
		}
	}
	
	/**
	 * Se intentara modificar el bloque que se encuentra en la posicion pasada. 
	 * Si la clave no se encuentra en dicho bloque se intentara remplazarla en 
	 * el padre.
	 * @param posicionBloque Posicion del bloque donde se intentar� hacer el 
	 * remplazo.
	 * @param claveNueva Clave nueva que remplzara a la vieja.
	 * @param claveRemplazar Clave a ser remplazada.
	 */
	void modificarClaveIndex(const long posicionBloque,const Clave &claveNueva,
		const Clave &claveRemplazar)
	{
		BloqueIndexSet<Clave> bloque(this->orden);
		
		// Se obtiene el bloque para la posicion pasada.
		this->getBloqueIndexSet(bloque,posicionBloque);

		//cout << "modificarClaveIndex(bloque=" << bloque <<
			//",claveNueva=" << claveNueva << ",claveRemplazar=" << 
			//claveRemplazar << ")" << endl;
		
		// Si el bloque contiene la clave a remplazar...
		if (bloque.find(claveRemplazar))
		{
			// ...se remplaza la clave en cuesti�n.
			// @todo: ver por que no reconoce este llamado si no se hace asi:
			bloque.Bloque<Clave>::remplazarClave(claveRemplazar,claveNueva);
			
			// Se asientan los cambios.
			this->actualizarBloqueIndexSet(bloque);
		}
		// Sino, en caso de que tenga padre...
		else if (bloque.tienePadre())
			// ...se intenta realizar el remplazo en el padre.
			this->modificarClaveIndex(bloque.getPadre(),claveNueva,
				claveRemplazar);
		else
			// Sino, tenemos un error.
			throw string("No existe la clave a remplazar en el index set.");
	}

	/**
	 * Trata de obtener una clave de alguno de los dos hermanos. 
	 * @param bloque Bloque para el cual se desea obtener la clave de alguno de 
	 * sus hermanos.
	 * @return true en caso de haber podido obtener la clave de alguno de sus 
	 * hermanos, sino false. 
	 */
	bool getClaveFromHermano(BloqueSequenceSet<Clave,Dato> &bloque)
	{		
		BloqueSequenceSet<Clave,Dato> hermano(this->orden);
		
		// En caso de tener bloque derecho...
		if (bloque.tieneBloqueDerecho())
		{
			// ...se obtiene el bloque derecho.
			this->getBloqueSequenceSet(hermano,bloque.getBloqueDerecho());
			
			// En caso de que dicho bloque no tenga la cantidad minima de 
			// claves...
			if (!hermano.tieneCantidadMinimaClaves())
			{
				hermano.first();
				
				// Se obtiene la primer clave del bloque derecho.
				Clave clave=hermano.getClaveActual();
				Dato dato=hermano.getDato();
					
				// Se inserta dicha clave en el bloque.
				bloque.insert(clave,dato);

				// Se elimina la clave del bloque derecho.
				hermano.erase(clave);
				
				// Se actualiza el bloque derecho.
				this->actualizarBloqueSequenceSet(hermano);
				
				// Se para sobre la primer clave del hermano (antes era la
				// segunda).
				hermano.first();
				
				// Se modifica la clave movida en el index set por la siguiente para 
				// el bloque derecho...
				this->modificarClaveIndex(hermano.getPadre(),
					hermano.getClaveActual(),clave);
								
				return true;
			}
		}

		// En caso de tener bloque izquierdo... 
		if (bloque.tieneBloqueIzquierdo())
		{
			// ...se obtiene el bloque izquierdo.
			this->getBloqueSequenceSet(hermano,bloque.getBloqueIzquierdo());
			
			// En caso de que dicho bloque no tenga la cantidad minima de 
			// claves...
			if (!hermano.tieneCantidadMinimaClaves())
			{
				// Se obtiene la ultima clave del bloque izquierdo.
				Clave clave=hermano.getUltimaClave();
				
				// Se obtiene la que ser� la segunda clave que ahora es la 
				// primer clave del bloque en cuesti�n.
				bloque.first();
				Clave segundaClave=bloque.getClaveActual();
				
				Dato dato=hermano.getDato();
					
				// Se inserta dicha clave en el bloque.
				bloque.insert(clave,dato);

				// Se elimina la clave del bloque izquierdo.
				hermano.erase(clave);
				
				// Se actualiza el bloque izquierdo.
				this->actualizarBloqueSequenceSet(hermano);
				
				// Se modifica la clave que quedo en segundo lugar en el index 
				// set, por la que ahora se encuentra en el primer lugar. 
				this->modificarClaveIndex(bloque.getPadre(),clave,segundaClave);
							
				return true;
			}
		}
		
		return false;
	}

	/**
	 * Trata de obtener una clave de alguno de los dos hermanos. 
	 * @param bloque Bloque para el cual se desea obtener la clave de alguno de 
	 * sus hermanos.
	 * @return true en caso de haber podido obtener la clave de alguno de sus 
	 * hermanos, sino false. 
	 */
	bool getClaveFromHermanoIndexSet(BloqueIndexSet<Clave> &bloque,const long nivel)
	{		
		//cout << "getClaveFromHermanoIndexSet(bloque=" << bloque << ", nivel=" << nivel << ")" << endl;
		
		BloqueIndexSet<Clave> hermano(this->orden);
		
		// En caso de tener bloque derecho...
		if (bloque.tieneBloqueDerecho())
		{
			// ...se obtiene el bloque derecho.
			this->getBloqueIndexSet(hermano,bloque.getBloqueDerecho());
			
			// En caso de que dicho bloque no tenga la cantidad minima de 
			// claves y sean del mismo padre...
			if ((!hermano.tieneCantidadMinimaClaves())&&
				(bloque.getPadre()==hermano.getPadre()))
			{
				BloqueIndexSet<Clave> padre;
				
				hermano.first();
				
				// Se obtiene la primer clave del bloque derecho.
				Clave clave=hermano.getClaveActual();
				
				// Se obtiene el primer hijo del bloque derecho.
				long posicionHijo=hermano.getHijoIzquierdoClaveActual();

				// Se elimina la clave del bloque derecho.
				hermano.erase(clave,posicionHijo);
				
				// Se obtiene el padre.
				this->getBloqueIndexSet(padre,bloque.getPadre());
				
				Clave claveRemplazada;
				
				// Se remplaza la clave que se encuentra entre los dos hijos y 
				// se obtiene la clave remplazada. 
				padre.remplazarClave(bloque.getPosicion(),hermano.getPosicion(),
					clave,claveRemplazada);
				
				// Se inserta dicha clave en el bloque junto con el hijo.
				bloque.insert(claveRemplazada,posicionHijo);
				
				
				// En caso de encontrarno en el �ltimo nivel del index set...
				if (nivel==this->ultimoNivelIndexSet())
				{
					// ...se actualiza el padre del bloque hijo que se 
					// encuentra en el sequence set.
					BloqueSequenceSet<Clave,Dato> hijo(this->orden);
					this->getBloqueSequenceSet(hijo,posicionHijo);
					hijo.setPadre(bloque);
					this->actualizarBloqueSequenceSet(hijo);
				}
				else
				{
					// Sino, se actualiza el padre del bloque hijo que se 
					// encuentra en el index set.
					BloqueIndexSet<Clave> hijo(this->orden);
					this->getBloqueIndexSet(hijo,posicionHijo);
					hijo.setPadre(bloque);
					this->actualizarBloqueIndexSet(hijo);
				}
				
				// Se actualiza el bloque derecho.
				this->actualizarBloqueIndexSet(hermano);
				
				// Se actualiza el padre.
				this->actualizarBloqueIndexSet(padre);
				
				return true;
			}
		}

		// En caso de tener bloque izquierdo... 
		if (bloque.tieneBloqueIzquierdo())
		{
			// ...se obtiene el bloque izquierdo.
			this->getBloqueIndexSet(hermano,bloque.getBloqueIzquierdo());
			
			// En caso de que dicho bloque no tenga la cantidad minima de 
			// claves y sean del mismo padre...
			if ((!hermano.tieneCantidadMinimaClaves())&&
				(bloque.getPadre()==hermano.getPadre()))
			{
				BloqueIndexSet<Clave> padre;
				
				// Se obtiene el padre.
				this->getBloqueIndexSet(padre,bloque.getPadre());
				
				// Se obtiene la �ltima clave del bloque izquierdo.
				Clave clave=hermano.getUltimaClave();
				
				// Se obtiene el �ltimo hijo del bloque izquierdo.
				long posicionHijo=hermano.getUltimoHijo();

				// Se elimina la clave del bloque izquierdo.
				hermano.erase(clave,posicionHijo);
				
				Clave claveRemplazada;
				
				// Se remplaza la clave que se encuentra entre los dos hijos y 
				// se obtiene la clave remplazada. 
				padre.remplazarClave(hermano.getPosicion(),
					clave,claveRemplazada);
				
				// Se inserta dicha clave en el bloque junto con el hijo izquierdo.
				bloque.insert(posicionHijo,claveRemplazada);
				
				
				// En caso de encontrarnos en el �ltimo nivel del index set...
				if (nivel==this->ultimoNivelIndexSet())
				{
					// ...se actualiza el padre del bloque hijo que se 
					// encuentra en el sequence set.
					BloqueSequenceSet<Clave,Dato> hijo(this->orden);
					this->getBloqueSequenceSet(hijo,posicionHijo);
					hijo.setPadre(bloque);
					this->actualizarBloqueSequenceSet(hijo);
				}
				else
				{
					// Sino, se actualiza el padre del bloque hijo que se 
					// encuentra en el index set.
					BloqueIndexSet<Clave> hijo(this->orden);
					this->getBloqueIndexSet(hijo,posicionHijo);
					hijo.setPadre(bloque);
					this->actualizarBloqueIndexSet(hijo);
				}
				
				// Se actualiza el bloque derecho.
				this->actualizarBloqueIndexSet(hermano);
				
				// Se actualiza el padre.
				this->actualizarBloqueIndexSet(padre);
				
				return true;
			}
		}
		
		return false;
	}

	/**
	 * Verifica si el bloque pasado es el primero del sequence set.
	 * @param bloque Bloque a ser validado.
	 * @return true si el bloque pasado es el primero del sequence set, sino 
	 * false.
	 */
	bool esPrimerBloqueSequenceSet(const BloqueSequenceSet<Clave,Dato> &bloque)
	{
		return this->primeroSequenceSet==bloque.getPosicion();
	}

	/**
	 * Se marca como borrado el bloque y se lo quita del cache.
	 * @param bloque Bloque a ser eliminado.
	 */
	void eliminarBloqueSequenceSet(const BloqueSequenceSet<Clave,Dato> &bloque)
	{
		// Se agrega el bloque al listado de bloques eliminados.
		this->borradosSequenceSet.push_back(bloque.getPosicion());

		// Se elimina el bloque del cache.
		this->cacheSequenceSet.erase(bloque.getPosicion());
	}

	/**
	 * Se elimina el bloque pasado del index set.
	 * @param bloque Bloque a ser eliminado del index set.
	 */
	void eliminarBloqueIndexSet(const BloqueIndexSet<Clave> &bloque)
	{
		// Se agrega el bloque al listado de bloques eliminados.
		this->borradosIndexSet.push_back(bloque.getPosicion());
		
		// Se elimina el bloque del cache.
		this->cacheIndexSet.erase(bloque.getPosicion());
	}

	/**
	 * Se unen los bloques pasados. Ambos bloques quedan con los datos del 
	 * bloque resultado de la union. Se elimina el bloque derecho. El bloque
	 * resultado de la union es el izquierdo.
	 * @param bloqueIzq Bloque izquierdo.
	 * @param bloqueDer Bloque derecho.
	 * @param nivel Nivel en el que se encuentran ambos bloques.
	 */
	void unirBloques(BloqueIndexSet<Clave> &bloqueIzq,
	BloqueIndexSet<Clave> &bloqueDer,const long nivel)
	{
		//cout << "unirBloques(bloqueIzq=" << bloqueIzq << ",bloqueDer=" << bloqueDer << ",nivel=" << nivel << ")" << endl;
		
		BloqueIndexSet<Clave> padre(this->orden);
		
		// Se pasan claves e hijos del bloque derecho al izquierdo.
		bloqueIzq.unir(bloqueDer);

		// Se obtiene el padre de ambos bloques (es el mismo).
		this->getBloqueIndexSet(padre,bloqueIzq.getPadre());
		
		// Se obtiene la clave del padre que tiene como hijo izquierdo a bloqueIzq.
		Clave claveDescendente=padre.getClaveHijoIzquierdo(
			bloqueIzq.getPosicion());
		
		// Se inserta dicha clave.
		bloqueIzq.Bloque<Clave>::insert(claveDescendente);
		
		// Se verifica si los hijos de bloqueIzq estan en el sequence set. Esto 
		// se hace antes de eliminar la clave del index set ya que la altura 
		// del arbol puede decrementarce.
		bool bloquesSequenceSet=((nivel+1)==this->altura);
		
		bool raizEliminada;
		
		this->actualizarBloqueIndexSet(bloqueIzq);
		
		// Se elimina la clave del padre junto con el hijo bloqueDer.
		this->eliminarClaveIndexSet(padre.getPosicion(),claveDescendente,
			bloqueDer.getPosicion(),nivel-1,raizEliminada);
		
		// Se obtiene el bloque del index set para en caso de que se haya 
		// actualizado el padre.
		this->getBloqueIndexSet(bloqueIzq,bloqueIzq.getPosicion());
			
		if (raizEliminada)
			bloqueIzq.quitarPadre();
			
		// Se actualiza el padre de los hijos de bloqueIzq.
		actualizarPadreHijos(bloqueIzq,bloquesSequenceSet);
		
		// Se actualizan los hermanos de los bloques hermanos de bloqueDer.
		if (bloqueDer.tieneBloqueDerecho())
		{
			BloqueIndexSet<Clave> nuevoBloqueDer(this->orden);
			this->getBloqueIndexSet(nuevoBloqueDer,bloqueDer.getBloqueDerecho());
			
			bloqueIzq.setHermano(nuevoBloqueDer);
			
			this->actualizarBloqueIndexSet(nuevoBloqueDer);
		}
		else
			bloqueIzq.quitarBloqueDerecho();
		
		// Se elimina bloqueDer del arbol.
		this->eliminarBloqueIndexSet(bloqueDer);
		
		bloqueDer=bloqueIzq;
	}

	/**
	 * Se une el bloque pasado con alguno de sus hermanos.
	 * @param bloque Bloque a ser unido con alguno de sus hermanos.
	 * @param nivel Nivel en el que se encuentra el bloque en cuestion.
	 * @pre No se puede obtener una clave de alguno de los bloques hermanos.
	 */
	void unirConHermanoIndexSet(BloqueIndexSet<Clave> &bloque,const long nivel)
	{
		// Se verifica que el bloque en cuesti�n no sea la raiz.
		if (nivel==1)
			throw string("No se puede unir el bloque raiz ya que no tiene hermanos.");
		
		bool unionRealizada=false;
		BloqueIndexSet<Clave> hermano(this->orden);
		
		// En caso de tener bloque derecho...  
		if (bloque.tieneBloqueDerecho())
		{
			// ...se obtiene el bloque derecho del sequence set.
			this->getBloqueIndexSet(hermano,bloque.getBloqueDerecho());
			
			// En caso de de que tengan mismo padre significa se encontro el 
			// hermano con el cual se realizara la union...
			if (unionRealizada=(bloque.getPadre()==hermano.getPadre()))
				// ...entonces se unen los bloques.
				this->unirBloques(bloque,hermano,nivel);
		}
		
		// Si todab�a no se ha hecho la union...
		if (!unionRealizada)
		{
			// ...se obtiene el bloque izquierdo del sequence set (que seguro 
			// debe tener mismo padre).
			this->getBloqueIndexSet(hermano,bloque.getBloqueIzquierdo());
			
			// Se realiza la union
			this->unirBloques(hermano,bloque,nivel);
		}
		
	}

	/**
	 * Se elimina la clave junto con el hijo del bloque pasado.
	 * @param posicionBloque Posicion del bloque del cual se deben eliminar la 
	 * clave y el hijo pasados.  
	 * @param clave Clave a eliminar.
	 * @param hijo Hijo a eliminar.
	 */
	void eliminarClaveIndexSet(const long posicionBloque,const Clave &clave,
		const long hijo,const long nivel,bool &raizEliminada)
	{
		raizEliminada=false;
		
		BloqueIndexSet<Clave> bloque(this->orden);
		
		this->getBloqueIndexSet(bloque,posicionBloque);
		
		//cout << "eliminarClaveIndexSet(bloque=" << bloque << ", clave=" << clave << ", hijo=" << hijo << ", nivel=" << nivel << ")" << endl;
		
		// En caso de ser el bloque raiz...
		if (this->raizIndexSet==posicionBloque)
		{
			// Se obtiene la posicion del bloque que puede llegar a sustituir 
			// la raiz.  
			bloque.first();
			long nuevaRaiz=bloque.getHijoIzquierdoClaveActual();
			
			// Se borra la clave y el hijo...
			bloque.erase(clave,hijo);
			
			// En caso de haber quedado vacia la raiz...
			if (bloque.vacio())
			{
				// ...se elimina el bloque...
				this->eliminarBloqueIndexSet(bloque);
				// ...se disminuye la altura del arbol...
				this->altura--;
				
				// En caso de que no queden bloques en el index set...
				if (this->altura==1)
					// ...se indica que no hay raiz.
					this->raizIndexSet=-1;
				else
					// Caso contrario, se setea la nueva raiz.
					this->raizIndexSet=nuevaRaiz;
					
				raizEliminada=true;
			}
		}
		else
		{
			// Se verifica si tiene la cantidad minima de claves.
			bool tieneCantidadMinimaClaves=bloque.tieneCantidadMinimaClaves();
			
			// Se eliminan la clave y el hijo del bloque. 
			bloque.erase(clave,hijo);
			
			// En caso de que la cantidad de claves sea minima...
			if (tieneCantidadMinimaClaves)
			{
				// Se intenta obtener una clave de alguno de los bloques a los 
				// laterales...
				if (!this->getClaveFromHermanoIndexSet(bloque,nivel))
					// En caso de no haber podido, se unen dos bloques.
					this->unirConHermanoIndexSet(bloque,nivel);
			}
		}
		
		this->actualizarBloqueIndexSet(bloque);
	}

	/**
	 * Se realiza la union de los bloques pasados, lo que implica pasar las 
	 * claves y datos de bloqueDer a bloqueIzq, eliminar la primer clave de
	 * bloqueDer del index set y eliminar bloqueDer del sequence set. Ambos
	 * bloques quedan con datos del bloque resultado de la union.
	 * @param bloqueIzq Bloque izquierdo.
	 * @param bloqueDer Bloque derecho.
	 */
	void unirBloques(BloqueSequenceSet<Clave,Dato> &bloqueIzq,
		BloqueSequenceSet<Clave,Dato> &bloqueDer)
	{
		// @todo: Eliminar lo que sigue:
		//cout << "unirBloques(bloqueIzq=" << bloqueIzq << ", bloqueDer=" << bloqueDer << ")" << endl;
		
		// En caso de no tener mismo padre... 
		if (bloqueIzq.getPadre()!=bloqueDer.getPadre())
			// ...se arroja una excepcion.
			throw string("Los bloques no se pueden unir porque tienen distinto padre");

		// Se obtiene la primer clave del bloque derecho.		
		bloqueDer.first();		
		Clave claveEliminar=bloqueDer.getClaveActual();
		
		// Se unen los bloques.
		bloqueIzq.unir(bloqueDer);
		
		bool raizEliminada;
		
		// Se actualiza el bloque del secuen set
		this->actualizarBloqueSequenceSet(bloqueIzq);
		
		// Se elimina la primer clave del bloque derecho del index set.
		this->eliminarClaveIndexSet(bloqueIzq.getPadre(),claveEliminar,
			bloqueDer.getPosicion(),this->altura-1,raizEliminada);

		// Se obtiene el bloque del sequence set para en caso de que se haya 
		// actualizado el padre. 		
		this->getBloqueSequenceSet(bloqueIzq,bloqueIzq.getPosicion());
			
		if (raizEliminada)
			bloqueIzq.quitarPadre();
		
		// En caso de que el bloque derecho tenga un bloque a su derecha... 
		if (bloqueDer.tieneBloqueDerecho())
		{
			BloqueSequenceSet<Clave,Dato> nuevoHermanoDerecho(this->orden);
		
			// ...se obtiene dicho bloque...	
			this->getBloqueSequenceSet(nuevoHermanoDerecho,
				bloqueDer.getBloqueDerecho());
			
			// ...se setea como hermano... 
			bloqueIzq.setHermano(nuevoHermanoDerecho);
			
			// ...se actualiza el nuevo hermano derecho.
			this->actualizarBloqueSequenceSet(nuevoHermanoDerecho);
		}
		else
			bloqueIzq.quitarBloqueDerecho();
		
		// Se elimina el bloque derecho del sequence set.
		this->eliminarBloqueSequenceSet(bloqueDer);
		
		bloqueDer=bloqueIzq;
	}

	/**
	 * Se une el bloque pasado con algun bloque hermano que tenga mismo padre.
	 * En caso de unirce con el bloque izquierdo se elimina el bloque del arbol
	 * y bloque pasa a ser el bloque a su izquierda.
	 * @param bloque Bloque que se unir� con alguno de sus hermanos.
	 */
	void unirConHermanoSequenceSet(BloqueSequenceSet<Clave,Dato> &bloque)
	{
		// @todo: Borrar lo que sigue:
//		cout << "unirConHermanoSequenceSet(bloque=" << bloque << ")" << endl;
		 	
		if (this->altura<2)
			throw string("Para unir bloques del sequence set la altura del ")+
				string("arbol debe ser mayor a 1.");
		
		bool unionRealizada=false;
		BloqueSequenceSet<Clave,Dato> hermano(this->orden);
		
		// En caso de tener bloque derecho...  
		if (bloque.tieneBloqueDerecho())
		{
			// ...se obtiene el bloque derecho del sequence set.
			this->getBloqueSequenceSet(hermano,bloque.getBloqueDerecho());
			
			// En caso de de que tengan mismo padre significa se encontro el 
			// hermano con el cual se realizara la union...
			if (unionRealizada=(bloque.getPadre()==hermano.getPadre()))
				// ...entonces se unen los bloques.
				this->unirBloques(bloque,hermano);
		}
		
		// Si todab�a no se ha hecho la union...
		if (!unionRealizada)
		{
			// ...se obtiene el bloque izquierdo del sequence set (que seguro 
			// debe tener mismo padre).
			this->getBloqueSequenceSet(hermano,bloque.getBloqueIzquierdo());
			
			// Se realiza la union
			this->unirBloques(hermano,bloque);
			
		}
	}

	void validarReferenciasPadreHijo(Bloque<Clave> &padre,Bloque<Clave> &hijo)
	{
		if (padre.getPosicion()!=hijo.getPadre())
			throw string("No coinciden las referencias de hijo y padre");
	}
	
	void verificarHermanos(Bloque<Clave> &bloque,const int nivel)
	{
		if (nivel<this->ultimoNivelIndexSet())
		{
			BloqueIndexSet<Clave> hermano(this->orden);

			if (bloque.tieneBloqueDerecho())
			{
				this->getBloqueIndexSet(hermano,bloque.getBloqueDerecho());
				if (bloque.getPosicion()!=hermano.getBloqueIzquierdo())
					throw string("Inconsistencia con hermano derecho");
			}

			if (bloque.tieneBloqueIzquierdo())
			{
				this->getBloqueIndexSet(hermano,bloque.getBloqueIzquierdo());
				if (bloque.getPosicion()!=hermano.getBloqueDerecho())
					throw string("Inconsistencia con hermano izquierdo");
			}
		}
		else
		{
			BloqueSequenceSet<Clave,Dato> hermano(this->orden);

			if (bloque.tieneBloqueDerecho())
			{
				this->getBloqueSequenceSet(hermano,bloque.getBloqueDerecho());
				if (bloque.getPosicion()!=hermano.getBloqueIzquierdo())
					throw string("Inconsistencia con hermano derecho");
			}

			if (bloque.tieneBloqueIzquierdo())
			{
				this->getBloqueSequenceSet(hermano,bloque.getBloqueIzquierdo());
				if (bloque.getPosicion()!=hermano.getBloqueDerecho())
					throw string("Inconsistencia con hermano izquierdo");
			}
		}
	}

	void consistentePreOrden(BloqueIndexSet<Clave> &bloque,const int nivel)
	{
		this->verificarHermanos(bloque,nivel);
		bloque.verificarCantidadHijos();
		
		if (nivel==1)
		{
			if (bloque.tienePadre())
				throw string("El bloque raiz tiene padre");
		}
		else if (nivel<this->ultimoNivelIndexSet())
		{	
			bloque.first();
			
			// En caso de no ser el utimo nivel del index set
			if (nivel<this->ultimoNivelIndexSet())
			{
				BloqueIndexSet<Clave> hijo(this->orden);
				this->getBloqueIndexSet(hijo,bloque.getHijoIzquierdoClaveActual());
				this->validarReferenciasPadreHijo(bloque,hijo);
				this->consistentePreOrden(hijo,nivel+1);
			}
			else
			{
				BloqueSequenceSet<Clave,Dato> hijo(this->orden);
				this->getBloqueSequenceSet(hijo,
					bloque.getHijoIzquierdoClaveActual());
				hijo.verificarDatos();
				this->verificarHermanos(hijo,nivel+1);
			}
			
			while (!bloque.eof())
			{
				if (nivel<this->ultimoNivelIndexSet())
				{
					BloqueIndexSet<Clave> hijo(this->orden);
					this->getBloqueIndexSet(hijo,
						bloque.getHijoDerechoClaveActual());
					this->validarReferenciasPadreHijo(bloque,hijo);
					this->consistentePreOrden(hijo,nivel+1);
				}
				else
				{
					BloqueSequenceSet<Clave,Dato> hijo(this->orden);
					this->getBloqueSequenceSet(hijo,
						bloque.getHijoDerechoClaveActual());
					hijo.verificarDatos();
					this->verificarHermanos(hijo,nivel+1);
				}
	
				bloque.next();
			}
		}
		
	}
	
	/**
	* Se escriben los datos del index set.
	*/
	void writeIndexSet()
	{
		this->indexSet.clear();
		this->indexSet.seekp(0);

		this->indexSet.write((char *)&(this->orden),sizeof(short));
		this->indexSet.write((char *)&(this->altura),sizeof(long));
		this->indexSet.write((char *)&(this->raizIndexSet),sizeof(long));
	}

	/**
	* Se escriben los datos del sequence set.
	*/
	void writeSequenceSet()
	{
		this->sequenceSet.clear();
		this->sequenceSet.seekp(0);

		this->sequenceSet.write((char *)&(this->primeroSequenceSet),sizeof(long));
	}

	/**
	* Se obtiene la raiz del index set.
	* @return Referencia al buffer con datos del bloque raiz del index set.
	*/
	void getRaizIndexSet(BloqueIndexSet<Clave> &bloque)
	{
		if (this->raizIndexSet<0)
			throw string("No existe raiz en el index set del arbol");

		this->getBloqueIndexSet(bloque,this->raizIndexSet);
	}

	/**
	* Se obtiene el primer bloque del sequence set.
	* @return Referencia al buffer con datos del primer bloque del sequence
	* set.
	*/
	void getPrimeroSequenceSet(BloqueSequenceSet<Clave,Dato> &bloque)
	{
		if (this->primeroSequenceSet<0)
			throw string("No existe primero en el sequence set del arbol");

		this->getBloqueSequenceSet(bloque,this->primeroSequenceSet);		
	}

	/**
	* Hace un split del bloque pasado agregando la clave pasada.
	* @param bloque Bloque que al agregar la clave pasada se har� un split.
	* @param clave Clave a ser agregada.
	* @param dato Dato a ser agregado.
	*/
	void splitBloqueSequenceSet(BloqueSequenceSet<Clave,Dato> &bloque,
		const Clave &clave,const Dato &dato)
	{
		BloqueSequenceSet<Clave,Dato> bloqueNuevo(this->orden);
		Clave claveAscendente;

		// Realiza el split del bloque.
		bloque.split(bloqueNuevo,claveAscendente,clave,dato);
				
		// Se setea el cursor al final del archivo con los datos del
		// sequence set.
		//this->sequenceSet.seekp(0,ios_base::end);
		
		// Se setea el cursor en un bloque vac�o del sequence set.
		this->setCursorBloqueVacioSequenceSet();		

		// Se setea la posicion al bloque nuevo.
		bloqueNuevo.setPosicion(this->sequenceSet.tellp());

		// En caso que el bloque al que se le hizo el split ya tenga un
		// bloque a su derecha...
		if (bloque.tieneBloqueDerecho())
		{
			BloqueSequenceSet<Clave,Dato> bloqueDerechoAnterior(this->orden);
			
			// Se obtiene el bloque a derecha.
			this->getBloqueSequenceSet(bloqueDerechoAnterior,
				bloque.getBloqueDerecho());			

			// Se setean como hermanos los bloques en cuestion.
			bloqueNuevo.setHermano(bloqueDerechoAnterior);

			// Se modifica el bloque derecho con la nueva referencia.
			this->actualizarBloqueSequenceSet(bloqueDerechoAnterior);
		}

		// Se setean como hermanos los bloques en cuestion.
		bloque.setHermano(bloqueNuevo);

		// Se actualiza el bloque a izquierda
		this->actualizarBloqueSequenceSet(bloque);

		// Se agrega el nuevo bloque.
		this->addBloqueSequenceSet(bloqueNuevo);

		// Se asciende la clave en el arbol.
		this->ascenderClave(claveAscendente,bloque,bloqueNuevo,true);
	}

	/**
	 * Se agrega un bloque al sequence set.
	 * @param bloque Bloque a ser agregado.
	 */
	void addBloqueIndexSet(BloqueIndexSet<Clave> &bloque)
	{
		// Se guarda el bloque
		bloque.write(this->indexSet);
		
		this->actualizarBloqueIndexSet(bloque);
	}

	/**
	* Se asciende la clave pasada en el arbol. Tener en cuenta que bloqueIzq y
	* bloqueDer tendran datos que pueden no corresponder con los que aparecen
	* en streamBloques luego de la ejecucion de este m�todo.
	* @param clave Clave a ser ascendida.
	* @param bloqueIzq Bloque a la izquierda de la clave
	* @param bloqueDer Bloque a la derecha de la clave.
	* @param bloquesSequenceSet Indica si bloqueIzq y bloqueDer son del 
	* sequence set o no. 
	*/
	void ascenderClave(const Clave &clave,Bloque<Clave> &bloqueIzq,
		Bloque<Clave> &bloqueDer,const bool bloquesSequenceSet)
	{
		// En caso de tener padre el bloque izquierdo...
		if (bloqueIzq.tienePadre())
		{
			BloqueIndexSet<Clave> padre(this->orden);

			// Se obtiene el bloque padre.
			this->getBloqueIndexSet(padre,bloqueIzq.getPadre());

			// En caso de estar lleno el padre...
			if (padre.lleno())
				splitBloqueIndexSet(padre,clave,bloqueIzq,bloqueDer,bloquesSequenceSet);
			else
			{
				// Sino se agrega la clave con los hijos al padre.
				padre.insert(clave,bloqueIzq.getPosicion(),
					bloqueDer.getPosicion());
					
				this->actualizarBloqueIndexSet(padre);
			}
			
			// Se actualiza el padre de cada hijo.
			this->actualizarPadreHijos(padre,bloquesSequenceSet);
		} 
		else
		{
			// Sino significa que el arbol crecera en altura.
			this->altura++;
			
			// Se setea el cursor al del index set.
			//this->indexSet.seekp(0,ios_base::end);
			
			// Se setea el cursor en un bloque vac�o del index set.
			this->setCursorBloqueVacioIndexSet();
			
			// Se setea la nueva raiz.
			this->raizIndexSet=this->indexSet.tellp();
			
			BloqueIndexSet<Clave> nuevoBloqueRaiz(this->orden);

			// Inserta la clave en el nuevo bloque junto con los hijos de dicha
			// clave.
			nuevoBloqueRaiz.insert(clave,bloqueIzq.getPosicion(),
				bloqueDer.getPosicion());

			// Se agrega el bloque al index set.
			this->addBloqueIndexSet(nuevoBloqueRaiz);

			// Se actualiza el padre de cada hijo de la nueva raiz.
			this->actualizarPadreHijos(nuevoBloqueRaiz,bloquesSequenceSet);
		}
	}

	/**
	* Hace un split del bloque pasado agregando la clave y los hijos pasados.
	* @param bloque Bloque que al agregar la clave pasada se har� un split.
	* @param clave Clave a ser agregada.
	* @param hijoIzq Hijo izquierdo de la clave pasada.
	* @param hijoDer Hijo derecho de la clave pasada.
	* @param bloquesSequenceSet Indica si hijoIzq e hijoDer son bloques del 
	* sequence set.
	*/
	void splitBloqueIndexSet(BloqueIndexSet<Clave> &bloque,const Clave &clave,
		Bloque<Clave> &hijoIzq,Bloque<Clave> &hijoDer,
		const bool bloquesSequenceSet)
	{
		BloqueIndexSet<Clave> bloqueNuevo(this->orden);
		Clave claveAscendente;

		// Se hace un split del bloque.
		bloque.split(bloqueNuevo,claveAscendente,clave,hijoIzq,hijoDer);

		// Se setea el cursor al final del archivo del index set.
		//this->indexSet.seekp(0,ios_base::end);
		
		// Se setea el cursor en un bloque vac�o del index set.
		this->setCursorBloqueVacioIndexSet();
		
		// Se setea la posicion al bloque nuevo.
		bloqueNuevo.setPosicion(this->indexSet.tellp());

		// En caso que el bloque al que se le hizo el split ya tenga un
		// bloque a su derecha...
		if (bloque.tieneBloqueDerecho())
		{
			BloqueIndexSet<Clave> bloqueDerechoAnterior(this->orden);
			
			// Se obtiene el bloque a derecha.
			this->getBloqueIndexSet(bloqueDerechoAnterior,
				bloque.getBloqueDerecho());			

			// Se setean como hermanos los bloques en cuestion.
			bloqueNuevo.setHermano(bloqueDerechoAnterior);

			// Se modifica el bloque derecho con la nueva referencia.
			this->actualizarBloqueIndexSet(bloqueDerechoAnterior);
		}

		// Se setean como hermanos los bloques en cuestion.
		bloque.setHermano(bloqueNuevo);

		// Se agrega el nuevo bloque.
		this->addBloqueIndexSet(bloqueNuevo);

		// Se actualiza el bloque.
		this->actualizarBloqueIndexSet(bloque);

		// Se actualizan los padres de los hijos de cada bloque.
		this->actualizarPadreHijos(bloque,bloquesSequenceSet);
		this->actualizarPadreHijos(bloqueNuevo,bloquesSequenceSet);

		// Se realiza el ascenso de la clave correspondiente.
		this->ascenderClave(claveAscendente,bloque,bloqueNuevo,false);
	}

	/**
	* Se actualiza el padre de los hijos del bloque pasado.
	* @param bloque Bloque del cual se obtendran los hijos para los cuales se
	* va a actualizar el padre.
	* @param bloquesSequenceSet Indica si los hijos de bloque se encuentran en 
	* el sequence set.
	*/
	void actualizarPadreHijos(BloqueIndexSet<Clave> &bloque,const bool bloquesSequenceSet)
	{
		// Se obtiene la primer clave del bloque.
		bloque.first();

		// En caso de que los hijos del bloque pertenezcan al sequence set...
		if (bloquesSequenceSet)
		{
			// Se obtiene el hijo izquierdo de dicha clave.
			BloqueSequenceSet<Clave,Dato> hijo(this->orden);
			
			this->getBloqueSequenceSet(hijo,
				bloque.getHijoIzquierdoClaveActual());
				
			// En caso de tener seteado otro padre...
			if (hijo.getPosicionPadre()!=bloque.getPosicion())
			{
				// ...se asigna el padre correspondiente.
				hijo.setPadre(bloque);
	
				// Se asientan los cambios.
				this->actualizarBloqueSequenceSet(hijo);
			}
	
			// Se realiza lo mismo para todos los hijos derechos de las claves del
			// bloque.
			while (!bloque.eof())
			{
				// Se limpia el bloque.
				hijo.clear();
	
				// Se obtiene el hijo derecho de la clave actual.
				this->getBloqueSequenceSet(hijo,
					bloque.getHijoDerechoClaveActual());
	
				// En caso de tener seteado otro padre...
				if (hijo.getPosicionPadre()!=bloque.getPosicion())
				{
					// ...se asigna el padre correspondiente.
					hijo.setPadre(bloque);
	
					// Se asientan los cambios.
					this->actualizarBloqueSequenceSet(hijo);
				}
	
				// Se va a la siguiente clave.
				bloque.next();
			}
		}
		else
		{
			BloqueIndexSet<Clave> hijo(this->orden);
			
			this->getBloqueIndexSet(hijo,
				bloque.getHijoIzquierdoClaveActual());

			// En caso de tener seteado otro padre...
			if (hijo.getPosicionPadre()!=bloque.getPosicion())
			{
				// ...se asigna el padre correspondiente.
				hijo.setPadre(bloque);
	
				// Se asientan los cambios.
				this->actualizarBloqueIndexSet(hijo);
			}
	
			// Se realiza lo mismo para todos los hijos derechos de las claves del
			// bloque.
			while (!bloque.eof())
			{
				// Se limpia el bloque.
				hijo.clear();
	
				// Se obtiene el hijo derecho de la clave actual.
				this->getBloqueIndexSet(hijo,bloque.getHijoDerechoClaveActual());
	
				// En caso de tener seteado otro padre...
				if (hijo.getPosicionPadre()!=bloque.getPosicion())
				{
					// ...se asigna el padre correspondiente.
					hijo.setPadre(bloque);
	
					// Se asientan los cambios.
					this->actualizarBloqueIndexSet(hijo);
				}
	
				// Se va a la siguiente clave.
				bloque.next();
			}
		}
	}

	/**
	 * Se muestra el arbol en pre orden.
	 * @param os stream de salida en el que se mostrara el arbol.
	 * @param bloque Bloque a ser mostrado.
	 * @param nivel Nivel del bloque pasado.
	 */
	void mostrarPreOrden(ostream &os,BloqueIndexSet<Clave> &bloque,const int nivel)
	{
		for (long i=1;i<nivel;i++)
			os << '\t';

		os << "(" << nivel << ") " << bloque << endl;

		bloque.first();

		// En caso de no ser el utimo nivel del index set
		if (nivel<this->ultimoNivelIndexSet())
		{
			BloqueIndexSet<Clave> hijo(this->orden);
			this->getBloqueIndexSet(hijo,bloque.getHijoIzquierdoClaveActual());
			mostrarPreOrden(os,hijo,nivel+1);
		}
		else
		{
			for (long i=0;i<nivel;i++)
				os << '\t';

			BloqueSequenceSet<Clave,Dato> hijo(this->orden);
			this->getBloqueSequenceSet(hijo,
				bloque.getHijoIzquierdoClaveActual());
			os << "(" << (nivel+1) << ") " << hijo << endl;
		}
		
		while (!bloque.eof())
		{
			if (nivel<this->ultimoNivelIndexSet())
			{
				BloqueIndexSet<Clave> hijo(this->orden);
				this->getBloqueIndexSet(hijo,
					bloque.getHijoDerechoClaveActual());
				mostrarPreOrden(os,hijo,nivel+1);
			}
			else
			{
				for (long i=0;i<nivel;i++)
					os << '\t';

				BloqueSequenceSet<Clave,Dato> hijo(this->orden);
				this->getBloqueSequenceSet(hijo,
					bloque.getHijoDerechoClaveActual());
				os << "(" << (nivel+1) << ") " << hijo << endl;
			}

			bloque.next();
		}

	}

};

#endif
